import org.w3c.dom.NodeList;

import java.util.HashMap;

// 实现LRU结构
// 测试链接 : https://leetcode.cn/problems/lru-cache/
public class LRU {

    class LRUCache {

        class DoubleNode{
            public int K;
            public int V;
            public DoubleNode last;
            public DoubleNode next;

            public DoubleNode(int k, int v){
                this.K = k;
                this.V = v;
            }
        }

        class DoubleList{
            public DoubleNode head;
            public DoubleNode tail;

            public DoubleList(){
                head = null;
                tail = null;
            }

            public void addNode(DoubleNode node ) {
                if(node == null){
                    return;
                }
                if(head == null) {  //首次加入
                    head = node;
                    tail = node;
                }else{
                    node.last = tail;
                    tail.next = node;
                    tail = node;
                }
            }

            public void removeToTail(DoubleNode node) {
                if(node == tail) {  //在尾部就不用移动
                    return;
                }
                if(node == head){
                    head = head.next;  //头结点变成下一个
                    head.last = null;

                }else{
                    node.last.next = node.next;
                    node.next.last = node.last;
                }
                node.last = tail;  //链接到尾结点上
                tail.next = node;
                node.next = null;
                tail = node;
            }

            public DoubleNode removeHead() {
                if(head == null) {
                    return null;
                }

                DoubleNode node = head;
                if(head == tail){
                    head = null;
                    tail = null;
                }else {
                    head = head.next;
                    head.last = null;
                }
                return node;
            }

        }

        public HashMap<Integer,DoubleNode> map;
        public DoubleList doubleList;
        public int cap;

        public LRUCache(int capacity) {
            map = new HashMap<>();
            doubleList = new DoubleList();
            cap = capacity;
        }

        public int get(int key) {
            if(!map.containsKey(key)){
                return -1;
            }
            DoubleNode node = map.get(key);
            doubleList.removeToTail(node);   //访问一次后将这个结点移动到尾结点上
            return node.V;
        }

        public void put(int key, int value) {
            if(map.containsKey(key)) {  //key已存在
                DoubleNode node = map.get(key);
                node.V = value;
                doubleList.removeToTail(node);
                return;
            }
            //判断空间是否已经满
            if(map.size() == cap ){
                DoubleNode node = doubleList.removeHead();  //去除双链表的头结点
                map.remove(node.K);  //移除map中的该结点
            }
            //此时空间还有
            DoubleNode node = new DoubleNode(key,value);
            doubleList.addNode(node);
            map.put(key,node);
        }
    }

}
